home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2002 #11 / Amiga Plus CD - 2002 - No. 11.iso / Tools / Development / libogg / libvorbis-1.0rc3 / lib / bitrate.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-10-27  |  19.5 KB  |  622 lines
  1. /********************************************************************
  2.  *                                                                  *
  3.  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
  4.  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
  5.  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
  6.  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
  7.  *                                                                  *
  8.  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2001             *
  9.  * by the XIPHOPHORUS Company http://www.xiph.org/                  *
  10.  *                                                                  *
  11.  ********************************************************************
  12.  
  13.  function: bitrate tracking and management
  14.  last mod: $Id: bitrate.c,v 1.9 2001/12/23 11:54:49 xiphmont Exp $
  15.  
  16.  ********************************************************************/
  17.  
  18. #include <stdio.h>
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #include <math.h>
  22. #include <ogg/ogg.h>
  23. #include "vorbis/codec.h"
  24. #include "codec_internal.h"
  25. #include "os.h"
  26. #include "bitrate.h"
  27.  
  28.  
  29. static long BINBITS(bitrate_manager_state *bm,long pos,long inbin){
  30.   int bins=bm->queue_bins;
  31.   int bin=((inbin&0x7fffffffUL)>>BITTRACK_BPT);
  32.   ogg_uint32_t lobits=0;
  33.   ogg_uint32_t hibits=0;
  34.   ogg_uint32_t bitdel;
  35.   
  36.   if(bin>0)lobits=bm->queue_binned[pos*bins+bin-1];
  37.   if(bin<bins)
  38.     hibits=bm->queue_binned[pos*bins+bin];
  39.   else
  40.     hibits=lobits;
  41.  
  42.   bitdel=hibits-lobits;
  43.  
  44.   return(lobits+bitdel*(inbin&((1<<BITTRACK_BPT)-1))/(1<<BITTRACK_BPT));
  45.  
  46. }
  47.  
  48. #define LIMITBITS(pos,bin) ((bin)>-bins?\
  49.                  bm->minmax_binstack[(pos)*bins*2+((bin)+bins)-1]:0)
  50.  
  51. static long LACING_ADJUST(long bits){
  52.   int addto=((bits+7)/8+1)/256+1;
  53.   return( ((bits+7)/8+addto)*8 );
  54. }
  55.  
  56. static double floater_interpolate(bitrate_manager_state *bm,vorbis_info *vi,
  57.                   double desired_rate){
  58.   int bin=bm->avgfloat*BITTRACK_DIVISOR-1.;
  59.   double lobitrate;
  60.   double hibitrate;
  61.   
  62.   lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
  63.   while(lobitrate>desired_rate && bin>0){
  64.     bin--;
  65.     lobitrate=(double)(bin==0?0:bm->avg_binacc[bin-1])/bm->avg_sampleacc*vi->rate;
  66.   }
  67.  
  68.   hibitrate=(double)(bin>=bm->queue_bins?bm->avg_binacc[bm->queue_bins-1]:
  69.              bm->avg_binacc[bin])/bm->avg_sampleacc*vi->rate;
  70.   while(hibitrate<desired_rate && bin<bm->queue_bins){
  71.     bin++;
  72.     if(bin<bm->queue_bins)
  73.       hibitrate=(double)bm->avg_binacc[bin]/bm->avg_sampleacc*vi->rate;
  74.   }
  75.  
  76.   /* interpolate */
  77.   if(bin==bm->queue_bins){
  78.     return bin/(double)BITTRACK_DIVISOR;
  79.   }else{
  80.     double delta=(desired_rate-lobitrate)/(hibitrate-lobitrate);
  81.     return (bin+delta)/BITTRACK_DIVISOR;
  82.   }
  83. }
  84.  
  85. /* try out a new limit */
  86. static long limit_sum(bitrate_manager_state *bm,int limit){
  87.   int i=bm->minmax_stackptr;
  88.   long acc=bm->minmax_acctotal;
  89.   long bins=bm->queue_bins;
  90.   
  91.   acc-=LIMITBITS(i,0);
  92.   acc+=LIMITBITS(i,limit);
  93.  
  94.   while(i-->0){
  95.     if(bm->minmax_limitstack[i]<=limit)break;
  96.     acc-=LIMITBITS(i,bm->minmax_limitstack[i]);
  97.     acc+=LIMITBITS(i,limit);
  98.   }
  99.   return(acc);
  100. }
  101.  
  102. /* compute bitrate tracking setup, allocate circular packet size queue */
  103. void vorbis_bitrate_init(vorbis_info *vi,bitrate_manager_state *bm){
  104.   int i;
  105.   codec_setup_info *ci=vi->codec_setup;
  106.   bitrate_manager_info *bi=&ci->bi;
  107.   long maxlatency;
  108.  
  109.   memset(bm,0,sizeof(*bm));
  110.   
  111.   if(bi){
  112.     
  113.     bm->avg_sampledesired=bi->queue_avg_time*vi->rate;
  114.     bm->avg_centerdesired=bi->queue_avg_time*vi->rate*bi->queue_avg_center;
  115.     bm->minmax_sampledesired=bi->queue_minmax_time*vi->rate;
  116.     
  117.     /* first find the max possible needed queue size */
  118.     maxlatency=max(bm->avg_sampledesired-bm->avg_centerdesired,
  119.            bm->minmax_sampledesired)+bm->avg_centerdesired;
  120.     
  121.     if(maxlatency>0 &&
  122.        (bi->queue_avgmin>0 || bi->queue_avgmax>0 || bi->queue_hardmax>0 ||
  123.     bi->queue_hardmin>0)){
  124.       long maxpackets=maxlatency/(ci->blocksizes[0]>>1)+3;
  125.       long bins=BITTRACK_DIVISOR*ci->passlimit[ci->coupling_passes-1];
  126.       
  127.       bm->queue_size=maxpackets;
  128.       bm->queue_bins=bins;
  129.       bm->queue_binned=_ogg_malloc(maxpackets*bins*sizeof(*bm->queue_binned));
  130.       bm->queue_actual=_ogg_malloc(maxpackets*sizeof(*bm->queue_actual));
  131.       
  132.       if((bi->queue_avgmin>0 || bi->queue_avgmax>0) &&
  133.      bi->queue_avg_time>0){
  134.     
  135.     bm->avg_binacc=_ogg_malloc(bins*sizeof(*bm->avg_binacc));
  136.     bm->avgfloat=bi->avgfloat_initial;
  137.     
  138.     
  139.       }else{
  140.     bm->avg_tail= -1;
  141.       }
  142.       
  143.       if((bi->queue_hardmin>0 || bi->queue_hardmax>0) &&
  144.      bi->queue_minmax_time>0){
  145.     
  146.     bm->minmax_binstack=_ogg_calloc((bins+1)*bins*2,
  147.                     sizeof(bm->minmax_binstack));
  148.     bm->minmax_posstack=_ogg_calloc((bins+1),
  149.                       sizeof(bm->minmax_posstack));
  150.     bm->minmax_limitstack=_ogg_calloc((bins+1),
  151.                       sizeof(bm->minmax_limitstack));
  152.       }else{
  153.     bm->minmax_tail= -1;
  154.       }
  155.       
  156.       /* space for the packet queueing */
  157.       bm->queue_packet_buffers=calloc(maxpackets,sizeof(*bm->queue_packet_buffers));
  158.       bm->queue_packets=calloc(maxpackets,sizeof(*bm->queue_packets));
  159.       for(i=0;i<maxpackets;i++)
  160.     oggpack_writeinit(bm->queue_packet_buffers+i);
  161.       
  162.     }else{
  163.       bm->queue_packet_buffers=calloc(1,sizeof(*bm->queue_packet_buffers));
  164.       bm->queue_packets=calloc(1,sizeof(*bm->queue_packets));
  165.       oggpack_writeinit(bm->queue_packet_buffers);
  166.     }      
  167.   }
  168. }
  169.  
  170. void vorbis_bitrate_clear(bitrate_manager_state *bm){
  171.   int i;
  172.   if(bm){
  173.     if(bm->queue_binned)_ogg_free(bm->queue_binned);
  174.     if(bm->queue_actual)_ogg_free(bm->queue_actual);
  175.     if(bm->avg_binacc)_ogg_free(bm->avg_binacc);
  176.     if(bm->minmax_binstack)_ogg_free(bm->minmax_binstack);
  177.     if(bm->minmax_posstack)_ogg_free(bm->minmax_posstack);
  178.     if(bm->minmax_limitstack)_ogg_free(bm->minmax_limitstack);
  179.     if(bm->queue_packet_buffers){
  180.       if(bm->queue_size==0){
  181.     oggpack_writeclear(bm->queue_packet_buffers);
  182.     _ogg_free(bm->queue_packet_buffers);
  183.       }else{
  184.     for(i=0;i<bm->queue_size;i++)
  185.       oggpack_writeclear(bm->queue_packet_buffers+i);
  186.     _ogg_free(bm->queue_packet_buffers);
  187.       }
  188.     }
  189.     if(bm->queue_packets)_ogg_free(bm->queue_packets);
  190.     memset(bm,0,sizeof(*bm));
  191.   }
  192. }
  193.  
  194. int vorbis_bitrate_managed(vorbis_block *vb){
  195.   vorbis_dsp_state      *vd=vb->vd;
  196.   backend_lookup_state  *b=vd->backend_state; 
  197.   bitrate_manager_state *bm=&b->bms;
  198.  
  199.   if(bm->queue_binned)return(1);
  200.   return(0);
  201. }
  202.  
  203. int vorbis_bitrate_maxmarkers(void){
  204.   return 8*BITTRACK_DIVISOR;
  205. }
  206.  
  207. /* finish taking in the block we just processed */
  208. int vorbis_bitrate_addblock(vorbis_block *vb){
  209.   int i; 
  210.   vorbis_block_internal *vbi=vb->internal;
  211.   vorbis_dsp_state      *vd=vb->vd;
  212.   backend_lookup_state  *b=vd->backend_state; 
  213.   bitrate_manager_state *bm=&b->bms;
  214.   vorbis_info           *vi=vd->vi;
  215.   codec_setup_info      *ci=vi->codec_setup;
  216.   bitrate_manager_info  *bi=&ci->bi;
  217.   int                    eofflag=vb->eofflag;
  218.   int                    head=bm->queue_head;
  219.   int                    next_head=head+1;
  220.   int                    bins=bm->queue_bins;
  221.   int                    minmax_head,new_minmax_head;
  222.   
  223.   ogg_uint32_t           *head_ptr;
  224.   oggpack_buffer          temp;
  225.  
  226.   if(!bm->queue_binned){
  227.     oggpack_buffer temp;
  228.     /* not a bitrate managed stream, but for API simplicity, we'll
  229.        buffer one packet to keep the code path clean */
  230.     
  231.     if(bm->queue_head)return(-1); /* one has been submitted without
  232.                                      being claimed */
  233.     bm->queue_head++;
  234.  
  235.     bm->queue_packets[0].packet=oggpack_get_buffer(&vb->opb);
  236.     bm->queue_packets[0].bytes=oggpack_bytes(&vb->opb);
  237.     bm->queue_packets[0].b_o_s=0;
  238.     bm->queue_packets[0].e_o_s=vb->eofflag;
  239.     bm->queue_packets[0].granulepos=vb->granulepos;
  240.     bm->queue_packets[0].packetno=vb->sequence; /* for sake of completeness */
  241.  
  242.     memcpy(&temp,bm->queue_packet_buffers,sizeof(vb->opb));
  243.     memcpy(bm->queue_packet_buffers,&vb->opb,sizeof(vb->opb));
  244.     memcpy(&vb->opb,&temp,sizeof(vb->opb));
  245.  
  246.     return(0);
  247.   }
  248.  
  249.   /* add encoded packet to head */
  250.   if(next_head>=bm->queue_size)next_head=0;
  251.   head_ptr=bm->queue_binned+bins*head;
  252.  
  253.   /* is there room to add a block? In proper use of the API, this will
  254.      never come up... but guard it anyway */
  255.   if(next_head==bm->avg_tail || next_head==bm->minmax_tail)return(-1);
  256.  
  257.   /* add the block to the toplevel queue */
  258.   bm->queue_head=next_head;
  259.   bm->queue_actual[head]=(vb->W?0x80000000UL:0);
  260.  
  261.   /* buffer packet fields */
  262.   bm->queue_packets[head].packet=oggpack_get_buffer(&vb->opb);
  263.   bm->queue_packets[head].bytes=oggpack_bytes(&vb->opb);
  264.   bm->queue_packets[head].b_o_s=0;
  265.   bm->queue_packets[head].e_o_s=vb->eofflag;
  266.   bm->queue_packets[head].granulepos=vb->granulepos;
  267.   bm->queue_packets[head].packetno=vb->sequence; /* for sake of completeness */
  268.  
  269.   /* swap packet buffers */
  270.   memcpy(&temp,bm->queue_packet_buffers+head,sizeof(vb->opb));
  271.   memcpy(bm->queue_packet_buffers+head,&vb->opb,sizeof(vb->opb));
  272.   memcpy(&vb->opb,&temp,sizeof(vb->opb));
  273.  
  274.   /* save markers */
  275.   memcpy(head_ptr,vbi->packet_markers,sizeof(*head_ptr)*bins);
  276.  
  277.   if(bm->avg_binacc)
  278.     new_minmax_head=minmax_head=bm->avg_center;
  279.   else
  280.     new_minmax_head=minmax_head=head;
  281.  
  282.   /* the average tracking queue is updated first; its results (if it's
  283.      in use) are taken into account by the min/max limiter (if min/max
  284.      is in use) */
  285.   if(bm->avg_binacc){
  286.     unsigned long desired_center=bm->avg_centerdesired;
  287.     if(eofflag)desired_center=0;
  288.  
  289.     /* update the avg head */
  290.     for(i=0;i<bins;i++)
  291.       bm->avg_binacc[i]+=LACING_ADJUST(head_ptr[i]);
  292.     bm->avg_sampleacc+=ci->blocksizes[vb->W]>>1;
  293.     bm->avg_centeracc+=ci->blocksizes[vb->W]>>1;
  294.  
  295.     if(bm->avg_sampleacc>bm->avg_sampledesired || eofflag){
  296.  
  297.       /* update the avg center */
  298.       if(bm->avg_centeracc>desired_center){
  299.     /* choose the new average floater */
  300.     int samples=ci->blocksizes[vb->W]>>1;
  301.     double upper=floater_interpolate(bm,vi,bi->queue_avgmax);
  302.     double lower=floater_interpolate(bm,vi,bi->queue_avgmin);
  303.     double new=bi->avgfloat_initial,slew;
  304.     int bin;
  305.     
  306.     if(upper>0. && upper<new)new=upper;
  307.     if(lower<bi->avgfloat_minimum)
  308.       lower=bi->avgfloat_minimum;
  309.     if(lower>new)new=lower;
  310.     
  311.     slew=(new-bm->avgfloat)/samples*vi->rate;
  312.     
  313.     if(slew<bi->avgfloat_downslew_max)
  314.       new=bm->avgfloat+bi->avgfloat_downslew_max/vi->rate*samples;
  315.     if(slew>bi->avgfloat_upslew_max)
  316.       new=bm->avgfloat+bi->avgfloat_upslew_max/vi->rate*samples;
  317.     
  318.     bm->avgfloat=new;
  319.  
  320.     /* apply the average floater to new blocks */
  321.     bin=bm->avgfloat*(BITTRACK_DIVISOR<<BITTRACK_BPT);
  322.     
  323.     while(bm->avg_centeracc>desired_center){
  324.       samples=ci->blocksizes[bm->queue_actual[bm->avg_center]&
  325.                 0x80000000UL?1:0]>>1;
  326.       
  327.       bm->queue_actual[bm->avg_center]|=bin;
  328.       
  329.       bm->avg_centeracc-=samples;
  330.       bm->avg_center++;
  331.       if(bm->noisetrigger_postpone)bm->noisetrigger_postpone-=samples;
  332.       if(bm->avg_center>=bm->queue_size)bm->avg_center=0;
  333.     }
  334.     new_minmax_head=bm->avg_center;
  335.     
  336.     /* track noise bias triggers and noise bias */
  337.     if(bm->avgfloat<bi->avgfloat_noise_lowtrigger)
  338.       bm->noisetrigger_request+=1.f;
  339.     else
  340.       if(bm->noisetrigger_request>0. && bm->avgnoise>0.)
  341.         bm->noisetrigger_request-=.2f;
  342.     
  343.     if(bm->avgfloat>bi->avgfloat_noise_hightrigger)
  344.       bm->noisetrigger_request-=1.f;
  345.     else
  346.       if(bm->noisetrigger_request<0 && bm->avgnoise<0.)
  347.         bm->noisetrigger_request+=.2f;
  348.     
  349.     if(bm->noisetrigger_postpone<=0){
  350.       if(bm->noisetrigger_request<0.){
  351.         bm->avgnoise-=1.f;
  352.         if(-bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
  353.           bm->avgnoise-=1.f;
  354.         bm->noisetrigger_postpone=bm->avg_sampleacc/2;
  355.       }
  356.       if(bm->noisetrigger_request>0.){
  357.         bm->avgnoise+=1.f;
  358.         if(bm->noisetrigger_request>(signed long)(bm->avg_sampleacc)/2)
  359.           bm->avgnoise+=1.f;
  360.         bm->noisetrigger_postpone=bm->avg_sampleacc/2;
  361.       }
  362.       
  363.       /* we generally want the noise bias to drift back to zero */
  364.       bm->noisetrigger_request=0.f;
  365.       if(bm->avgnoise>0)
  366.         bm->noisetrigger_request= -1.;
  367.       if(bm->avgnoise<0)
  368.         bm->noisetrigger_request= +1.;
  369.       
  370.       if(bm->avgnoise<bi->avgfloat_noise_minval)
  371.         bm->avgnoise=bi->avgfloat_noise_minval;
  372.       if(bm->avgnoise>bi->avgfloat_noise_maxval)
  373.         bm->avgnoise=bi->avgfloat_noise_maxval;
  374.     }
  375.       }
  376.       
  377.       /* update the avg tail if needed */
  378.       while(bm->avg_sampleacc>bm->avg_sampledesired){
  379.     int samples=
  380.       ci->blocksizes[bm->queue_actual[bm->avg_tail]&0x80000000UL?1:0]>>1;
  381.     for(i=0;i<bm->queue_bins;i++)
  382.       bm->avg_binacc[i]-=LACING_ADJUST(bm->queue_binned[bins*bm->avg_tail+i]);
  383.     bm->avg_sampleacc-=samples;
  384.     bm->avg_tail++;
  385.     if(bm->avg_tail>=bm->queue_size)bm->avg_tail=0;
  386.       }
  387.       
  388.       
  389.     }
  390.   }else{
  391.     /* if we're not using an average tracker, the 'float' is nailed to
  392.        the avgfloat_initial value.  It needs to be set for the min/max
  393.        to deal properly */
  394.     long bin=bi->avgfloat_initial*(BITTRACK_DIVISOR<<BITTRACK_BPT);
  395.     bm->queue_actual[head]|=bin;
  396.     new_minmax_head=next_head;
  397.   }    
  398.   
  399.   /* update the min/max queues and enforce limits */
  400.   if(bm->minmax_binstack){
  401.     unsigned long sampledesired=eofflag?0:bm->minmax_sampledesired;
  402.     
  403.     /* add to stack recent */
  404.     while(minmax_head!=new_minmax_head){
  405.       unsigned int i;
  406.       int samples=ci->blocksizes[bm->queue_actual[minmax_head]&
  407.                 0x80000000UL?1:0]>>1;
  408.       
  409.     /* the construction here is not parallel to the floater's
  410.        stack.  
  411.  
  412.        floater[bin-1]  <-> floater supported at bin
  413.        ...
  414.        floater[0]      <-> floater supported at 1
  415.        supported at zero is implicit.  
  416.        the BINBITS macro performs offsetting
  417.  
  418.      
  419.       bin  minmax[bin*2-1] <-> floater supported at bin
  420.        ...
  421.     1  minmax[bin]     <-> floater supported at 1
  422.     0  minmax[bin-1]   <-> no limit/support (limited to/supported at bin 0,
  423.                                              ie, no effect)
  424.        -1  minmax[bin-2]   <-> floater limited to bin-1
  425.        ...
  426.     -bin+1  minmax[0]       <-> floater limited to 1
  427.         limited to zero (val= -bin) is implicit
  428.     */
  429.       for(i=0;i<(unsigned int)bins;i++){
  430.     bm->minmax_binstack[bm->minmax_stackptr*bins*2+bins+i]+=
  431.       LACING_ADJUST(
  432.       BINBITS(bm,minmax_head,
  433.           (bm->queue_actual[minmax_head]&0x7fffffffUL)>
  434.           ((i+1)<<BITTRACK_BPT)?
  435.           bm->queue_actual[minmax_head]:
  436.           ((i+1)<<BITTRACK_BPT)));
  437.     
  438.     bm->minmax_binstack[bm->minmax_stackptr*bins*2+i]+=
  439.       LACING_ADJUST(
  440.       BINBITS(bm,minmax_head,
  441.           (bm->queue_actual[minmax_head]&0x7fffffffUL)<
  442.           ((i+1)<<BITTRACK_BPT)?
  443.           bm->queue_actual[minmax_head]:
  444.           ((i+1)<<BITTRACK_BPT)));
  445.       }
  446.       
  447.       bm->minmax_posstack[bm->minmax_stackptr]=minmax_head; /* not one
  448.                                    past
  449.                                    like
  450.                                    typical */
  451.       bm->minmax_limitstack[bm->minmax_stackptr]=0;
  452.       bm->minmax_sampleacc+=samples;
  453.       bm->minmax_acctotal+=
  454.     LACING_ADJUST(BINBITS(bm,minmax_head,bm->queue_actual[minmax_head]));
  455.       
  456.       minmax_head++;
  457.       if(minmax_head>=bm->queue_size)minmax_head=0;
  458.     }
  459.     
  460.     /* check limits, enforce changes */
  461.     if(bm->minmax_sampleacc>sampledesired){
  462.       double bitrate=(double)bm->minmax_acctotal/bm->minmax_sampleacc*vi->rate;
  463.       int limit=0;
  464.       
  465.       if((bi->queue_hardmax>0 && bitrate>bi->queue_hardmax) || 
  466.      (bi->queue_hardmin>0 && bitrate<bi->queue_hardmin)){
  467.     int newstack;
  468.     int stackctr;
  469.     long bitsum=limit_sum(bm,0);
  470.  
  471.     bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
  472.  
  473.     /* we're off rate.  Iteratively try out new hard floater
  474.            limits until we find one that brings us inside.  Here's
  475.            where we see the whole point of the limit stacks.  */
  476.     if(bi->queue_hardmax>0 && bitrate>bi->queue_hardmax){
  477.       for(limit=-1;limit>-bins;limit--){
  478.         long bitsum=limit_sum(bm,limit);
  479.         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
  480.         if(bitrate<=bi->queue_hardmax)break;
  481.       }
  482.     }else if(bitrate<bi->queue_hardmin){
  483.       for(limit=1;limit<bins;limit++){
  484.         long bitsum=limit_sum(bm,limit);
  485.         bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
  486.         if(bitrate>=bi->queue_hardmin)break;
  487.       }
  488.       if(bitrate>bi->queue_hardmax)limit--;
  489.     }
  490.  
  491.     for(i=limit-1;i>-bins;i--){
  492.       long bitsum=limit_sum(bm,i);
  493.       bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
  494.     }
  495.  
  496.     bitsum=limit_sum(bm,limit);
  497.     bitrate=(double)bitsum/bm->minmax_sampleacc*vi->rate;
  498.  
  499.     /* trace the limit backward, stop when we see a lower limit */
  500.     newstack=bm->minmax_stackptr-1;
  501.     while(newstack>=0){
  502.       if(bm->minmax_limitstack[newstack]<limit)break;
  503.       newstack--;
  504.     }
  505.     
  506.     /* update bit counter with new limit and replace any stack
  507.            limits that have been replaced by our new lower limit */
  508.     stackctr=bm->minmax_stackptr;
  509.     while(stackctr>newstack){
  510.       bm->minmax_acctotal-=
  511.         LIMITBITS(stackctr,bm->minmax_limitstack[stackctr]);
  512.       bm->minmax_acctotal+=LIMITBITS(stackctr,limit);
  513.  
  514.       if(stackctr<bm->minmax_stackptr)
  515.         for(i=0;i<bins*2;i++)
  516.           bm->minmax_binstack[stackctr*bins*2+i]+=
  517.           bm->minmax_binstack[(stackctr+1)*bins*2+i];
  518.  
  519.       stackctr--;
  520.     }
  521.     stackctr++;
  522.     bm->minmax_posstack[stackctr]=bm->minmax_posstack[bm->minmax_stackptr];
  523.     bm->minmax_limitstack[stackctr]=limit;
  524.  
  525.     /* set up new blank stack entry */
  526.     stackctr++;
  527.     bm->minmax_stackptr=stackctr;
  528.     memset(&bm->minmax_binstack[stackctr*bins*2],
  529.            0,
  530.            sizeof(*bm->minmax_binstack)*bins*2);
  531.     bm->minmax_limitstack[stackctr]=0;
  532.     bm->minmax_posstack[stackctr]=-1;
  533.     
  534.       }
  535.     }
  536.     
  537.     /* remove from tail */
  538.     while(bm->minmax_sampleacc>sampledesired){
  539.       int samples=
  540.     ci->blocksizes[bm->queue_actual[bm->minmax_tail]&0x80000000UL?1:0]>>1;
  541.       int actual=bm->queue_actual[bm->minmax_tail]&0x7fffffffUL;
  542.  
  543.       for(i=0;i<bins;i++){
  544.     bm->minmax_binstack[bins+i]-= /* always comes off the stack bottom */
  545.       LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
  546.                 actual>((i+1)<<BITTRACK_BPT)?
  547.                 actual:((i+1)<<BITTRACK_BPT)));
  548.     bm->minmax_binstack[i]-= 
  549.       LACING_ADJUST(BINBITS(bm,bm->minmax_tail,
  550.                 actual<((i+1)<<BITTRACK_BPT)?
  551.                 actual:((i+1)<<BITTRACK_BPT)));
  552.       }
  553.  
  554.       /* always perform in this order; max overrules min */
  555.       if((bm->minmax_limitstack[0]<<BITTRACK_BPT)>actual)
  556.     actual=(bm->minmax_limitstack[0]<<BITTRACK_BPT);
  557.       if(((bins+bm->minmax_limitstack[0])<<BITTRACK_BPT)<actual)
  558.     actual=(bins+bm->minmax_limitstack[0])<<BITTRACK_BPT;
  559.  
  560.       bm->minmax_acctotal-=LACING_ADJUST(BINBITS(bm,bm->minmax_tail,actual));
  561.       bm->minmax_sampleacc-=samples;
  562.      
  563.       /* revise queue_actual to reflect the limit */
  564.       bm->queue_actual[bm->minmax_tail]&=0x80000000UL;
  565.       bm->queue_actual[bm->minmax_tail]|=actual;
  566.       
  567.       if(bm->minmax_tail==bm->minmax_posstack[0]){
  568.     /* the stack becomes a FIFO; the first data has fallen off */
  569.     memmove(bm->minmax_binstack,bm->minmax_binstack+bins*2,
  570.         sizeof(*bm->minmax_binstack)*bins*2*bm->minmax_stackptr);
  571.     memmove(bm->minmax_posstack,bm->minmax_posstack+1,
  572.         sizeof(*bm->minmax_posstack)*bm->minmax_stackptr);
  573.     memmove(bm->minmax_limitstack,bm->minmax_limitstack+1,
  574.         sizeof(*bm->minmax_limitstack)*bm->minmax_stackptr);
  575.     bm->minmax_stackptr--;
  576.       }
  577.       
  578.       bm->minmax_tail++;
  579.       if(bm->minmax_tail>=bm->queue_size)bm->minmax_tail=0;
  580.     }
  581.     
  582.     
  583.     bm->last_to_flush=bm->minmax_tail;
  584.   }else{
  585.     bm->last_to_flush=bm->avg_center;
  586.   }
  587.   if(eofflag)
  588.     bm->last_to_flush=bm->queue_head;
  589.   return(0);
  590. }
  591.  
  592. int vorbis_bitrate_flushpacket(vorbis_dsp_state *vd,ogg_packet *op){
  593.   backend_lookup_state  *b=vd->backend_state;
  594.   bitrate_manager_state *bm=&b->bms;
  595.  
  596.   if(bm->queue_size==0){
  597.     if(bm->queue_head==0)return(0);
  598.  
  599.     memcpy(op,bm->queue_packets,sizeof(*op));
  600.     bm->queue_head=0;
  601.  
  602.   }else{
  603.     long bin;
  604.     long bytes;
  605.  
  606.     if(bm->next_to_flush==bm->last_to_flush)return(0);
  607.  
  608.     bin=bm->queue_actual[bm->next_to_flush];
  609.     bytes=(BINBITS(bm,bm->next_to_flush,bin)+7)/8;
  610.     
  611.     memcpy(op,bm->queue_packets+bm->next_to_flush,sizeof(*op));
  612.  
  613.     if(bytes<op->bytes)op->bytes=bytes;
  614.  
  615.     bm->next_to_flush++;
  616.     if(bm->next_to_flush>=bm->queue_size)bm->next_to_flush=0;
  617.  
  618.   }
  619.  
  620.   return(1);
  621. }
  622.